home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6417 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: cs.ruu.nl!usenet
  2. From: wsldanke@cs.ruu.nl (Wessel Dankers)
  3. Newsgroups: comp.sys.amiga.programmer
  4. Subject: Re: scramble game algorithm?
  5. Date: 27 Mar 96 20:21:39 +0100
  6. Organization: Dept of Computer Science, Utrecht University, The Netherlands
  7. Message-ID: <1710.6660T1221T1979@cs.ruu.nl>
  8. References: <3157B388.3F20@sapiens.com> <3159875F.7951@p3.enzian.com>
  9. NNTP-Posting-Host: anx1p5.cc.ruu.nl
  10. X-Newsreader: THOR 2.22 (Amiga TCP/IP)
  11.  
  12. Jude Anthony <jude@p3.enzian.com> wrote:
  13. > Avi L. wrote:
  14. >> Hi there, i'm trying to figure out an algorithm for solving the
  15. >> famous scramble game, i've succeeded in solving most of the game
  16.  
  17. > You need a different algorythm, I think.  Forget the logic; this can be
  18. > easily solved with a simple tree.  Since there is no position from which
  19. > more than four pieces can move into the empty square, you create a tree
  20. > with four branches at each node.  A structure with four pointers will be
  21. > necessary; I would also include an array specifying the board position
  22. > after the move has been made and an integer specifying the array index of
  23. > the piece moved:
  24.  
  25. > Write a recursive function to tranverse this tree.  Every step, move each
  26. > possible tile into the space and create a new node for the new board
  27. > position.  Compare the node to previous board configurations to make sure
  28. > you're not duplicating your work.  Stop and return when there are no
  29. > non-repetetive board configurations, or you reach a node with a solved
  30. > board.
  31.  
  32. > If you actually create the entire tree (instead of stopping when you
  33. > reach your first solve), this algorythm gives you the added bonus of
  34. > being able to find the fewest moves necessary to solve the board.
  35.  
  36. This just *begs* for dynamic programming. I just wouldn't know how. :-)
  37.  
  38. --
  39. Wessel Dankers                 _\\|//_            <wsldanke@cs.ruu.nl>
  40.                                ///|\\\
  41. ----------------------------oOO--(_)---OOo----------------------------
  42. `Never imagine yourself not to be otherwise than what it might appear
  43. to others that what you were or might have been was not otherwise than
  44. what you had been would have appeared to them to be otherwise.'
  45.  
  46.